package 回溯;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
public class LeetCode690_员工的重要性 {
    /**
     *边界:
     * 下属为空 每次先加第一个下属的重要性
     * 按照相同的操作再去加下属的第一个下属的重要性
     */
    public int DFS(Map<Integer,Employee> info, int id) {
        // 当前员工的importance + 它的所有下属的importance
        Employee curE = info.get(id); // 拿到当前员工信息
        int sum = curE.importance; // 定义一个sum加和，来累加所有的重要度的和
        for (int subId : curE.subordinates) {
            sum += DFS(info,subId);
        }
        return sum;
    }
    public int getImportance(List<Employee> employees, int id) {
        if(employees.isEmpty()) {
            return 0;
        }
        // 这里用一个Map来存索引和信息的关系，因为List集合遍历时间复杂度过高
        Map<Integer,Employee> info = new HashMap<Integer,Employee>();
        for (Employee e : employees) {
            info.put(e.id,e);
        }
        return DFS(info,id);
    }
}
